/*
 * @lc app=leetcode.cn id=59 lang=cpp
 *
 * [59] 螺旋矩阵 II
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0));

        std::vector<int> direction = { 0, 1, 0, -1, 0 };
        int cyc = 0;

        //这是一个根据方向进行的 DFS
        sprialMatrix(direction, result, 0, 0, 1, cyc);
        return result;
    }

    void sprialMatrix(const std::vector<int>& direction,
        vector<vector<int>>& matrix, int i, int j, int start, int& cyc) {
        //所有方格填满, 则退出
        if(std::find_if(matrix.begin(), matrix.end(), [](const vector<int>& v) {
            return std::find_if(v.begin(), v.end(), [](int i){ return i == 0; }) != v.end();
        }) == matrix.end()) {
            return;
        }

        //注意, 这里判断下一个格子是否越界, 并且是否已访问
        int pi = i + direction[cyc];
        int pj = j + direction[cyc + 1];

        //若 下一个位置 越界 或者 已访问, 改变方向
        if ((pi >= matrix.size() || pi < 0) ||
            (pj >= matrix[i].size() || pj < 0) ||
            matrix[pi][pj] != 0) {
            cyc = (cyc + 1) % 4;
        }

        //直接填充, 不需要害怕越界问题
        matrix[i][j] = start;
        sprialMatrix(direction, matrix, 
            i + direction[cyc], 
            j + direction[cyc + 1], 
            start + 1, cyc);
    }
};
// @lc code=end

